%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Conclusion}~\label{chap:conclusion}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% overall summary
This thesis presented the Cardinal Execution Map as a framework for
performance modeling and prediction of program execution. The goal
of the CEM is to provide a common framework for characterizing program
behavior in a way that can be used for both static and dynamic
analysis.

% first contribution
The Cardinal execution modeling framework was described and three
specific representations of program execution in modern architectures
were introduced: Base, Input Composite and Thread Composite.
The CEMs were shown to accurately track program behavior.
Characteristics from the SPEC2000 benchmarks
showed a wide range of behaviors. Programs such as 164.gzip show
regular behavior whereas programs such as 197.parser showed
unpredictable, non-regular behavior. Similarities between CEMs
resulting from different compiler flags was explored using graph
similarity and graph clustering techniques.

% second contribution
The inherent properties of CEMs to enable temporal prediction and
input identification were examined. Using a Markov model predictor,
15 of 20 SPEC2000 programs were able to predict 1 to 10 time
stages out from a current point with 65\% accuracy. Input
identification using the CEM framework explored node-based and
path-based techniques to locate program execution within a unique
input in a program's composite graph. Node-based techniques
allowed almost all programs to be predicted using a small
node-set, while path-based techniques showed better performance
while requiring less time to identification. Input identification can be useful in
modern multi-core systems in special purpose versions of code.
Execution prediction can aid multi-core scheduling by predicting when
shared resources may become critical bottlenecks to system throughput.

% third contrbution
The CEM system has the ability to model interaction between programs
in a multi-context environment. A methodology for creating a CEM
representation of a multi-context run called the Merged CEM was presented.
Considerations of
the variable run time of programs was examined. The accuracy of this
multi-core representation was compared against an actual runs of
SPEC2000 benchmarks paired in an Intel Core 2 Duo. Results showed that in a
majority of runs, the majority of predictions correctly predicted the future
node state of the system.

% fourth contribution
Throughout the thesis, considerations for using the CEM at run time
are presented. The CEM system can be used to store information about
program behavior that can be used for a run-time system or the run-time
system can dynamically capture and store behavior into the CEM
format.

The trade-offs of approaches in terms of their use statically or dynamically
were discussed. Pivot clustering was used in this work as it is a fast
clustering algorithm that can be used at run time. K-means clustering is a
well-understood and widely used clustering algorithm though it lends itself to
offline static analysis as it is very computational. Two types of prediction
models were used in this work. First, a Markov model was used to predict the
future node state of a program. In the multi-context work, a most weighted edge
approach was used. The first order results of the two methods is the same but
the Markov Model presents alternate solutions whereas the most weighted edge
only give one solution. The Markov model is useful in static analysis and the
most weighted edge can be used to make run-time decisions.

% ending paragraph
Future performance increases in computer systems is not dependent only
on new hardware designs. Understanding program behavior is key to
increasing the performance. The Cardinal Execution Map fosters this
understanding of program behavior and has the ability to further
research and studies of computer systems.
